#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;


class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int wordcnt = words.size();
        int linecnt = 0;
        int ix=0,jx;
        vector<string> ans;

        while(ix < wordcnt){
            linecnt = 0;
            jx = ix;
            // 首先找出所能容纳的最大单词数
            while(jx<wordcnt && 
                linecnt + words[jx].size() <= maxWidth){
                linecnt += words[jx].size();
                linecnt += 1; // 单词间最少一个空格
                jx++;
            }
            // 此时单词从ix到jx，共有jx-ix个单词
            // cout<<jx-ix<<"   "<<linecnt<<endl;
            
            // 从ix-jx开始填一个字符串
            string str;
            if(jx - ix == 1){
                // 只有一个单词
                str += words[ix];
                str += string(maxWidth-words[ix].size(),' ');
            } else if(jx==wordcnt){
                // 最后一行
                for(int i=ix;i<jx-1;i++){
                    str += words[i]+" ";
                }
                str+= words[jx-1];
                str+= string(maxWidth-str.size(),' ');
            } else {
                // 此时有多个单词，需要满足两边对其
                int charsum = 0;
                for(int i=ix;i<jx;i++){
                    charsum += words[i].size();
                }
                // 需要如此多的空格
                int spacecnt = (maxWidth - charsum);

                // 需要填到 jx-ix-1个位置
                int eachspace = spacecnt / (jx-ix-1);
                int modspace = spacecnt % (jx-ix-1);
                int modcnt = 0;
                for(int i=ix;i<jx-1;i++){
                    str += words[i];
                    // 每一个填空格
                    str += string(eachspace,' ');
                    if(modcnt < modspace){
                        modcnt++;
                        str += ' ';
                    }
                }
                str+= words[jx-1];
            }
            // cout<<str<<endl;
            // cout<<str.size()<<endl;
            // cout<<endl;
            ans.push_back(str);
            ix = jx;
        }

        return ans;
    }
};

int main(){
    Solution solu;
    vector<string> words = {"What","must","be","acknowledgment","shall","be"};
    solu.fullJustify(words,16);
    words =  {"This", "is", "an", "example", "of", "text", "justification."};
    solu.fullJustify(words,16);
    words = {"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"};
    solu.fullJustify(words,20);
    return 0;
}